package com.cuz.daileetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Day57 {
    public static class MaximumContinuousSubarraySum {
        public static int solution1(int[] arr) {
            int len = arr.length;
            int[][] dp = new int[len][len];
            for (int i = 0; i < len; i++) {
                dp[i][i] = arr[i];
            }
            int max = Integer.MIN_VALUE;
            for (int row = 0; row < len; row++) {
                for (int col = row + 1; col < len; col++) {
                    dp[row][col] = dp[row][col - 1] + arr[col];
                    max = Math.max(max, dp[row][col]);
                }
            }
            return max;
        }

        public static void main(String[] args) {
            System.out.println(solution1(new int[]{-1, 3, 17, -7, 9, 5}));
            System.out.println(solution2(new int[]{-1, 3, 17, -7, 9, 5}));
        }

        public static int solution2(int[] arr) {
            int cur = 0;
            int max = Integer.MIN_VALUE;
            for (int temp : arr) {
                cur += temp;
                max = Math.max(max, cur);
                if (cur < 0) {
                    cur = 0;
                }
            }
            return max;
        }
    }

    public static class ThreeNumSum {
        public static List<List<Integer>> solution1(int[] arr) {
            if (arr == null || arr.length == 0) {
                return null;
            }
            Arrays.sort(arr);
            List<List<Integer>> res = new ArrayList<>();
            int len = arr.length;
            for (int start = 0; start < len - 2; start++) {
                if (arr[start] > 0) {
                    continue;
                }
                if (start > 0 && arr[start] == arr[start - 1]) {
                    continue;
                }
                int mid = start + 1;
                int end = arr.length - 1;
                while (mid < end) {
                    int tempRes = arr[start] + arr[mid] + arr[end];
                    if (tempRes == 0) {
                        res.add(Arrays.asList(arr[start], arr[mid], arr[end]));
                        mid++;
                        end--;
                        while (mid < end && arr[mid] == arr[mid - 1]) {
                            mid++;
                        }
                        while (mid < end && arr[end] == arr[end - 1]) {
                            end--;
                        }
                    } else if (tempRes > 0) {
                        end--;
                    } else {
                        mid++;
                    }
                }
            }
            return res;
        }

        public static void main(String[] args) {
            System.out.println(solution1(new int[]{-1, 0, 1, 2, -1, 4, -4}));
        }
    }

    public static int solution1(int[] arr, int k) {
        int res = Integer.MAX_VALUE;
        Arrays.sort(arr);
        for (int start = 0; start < arr.length - 2; start++) {
            int end = arr.length - 1;
            int mid = start + 1;
            while (mid < end) {
                int tempSum = arr[start] + arr[end] + arr[mid];
                if (tempSum == k) {
                    return k;
                }
                if (Math.abs(tempSum - k) < Math.abs(res - k)) {
                    res = tempSum;
                }
                if (tempSum > k) {
                    end--;
                    continue;
                }
                if (tempSum < k) {
                    mid++;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(solution1(new int[]{1, 2, 3, -3, 1, 6, 7}, -100));
    }

}
